package leetcode.code;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution513 implements IDebug {

	public int findBottomLeftValue(TreeNode root) {
		return this.f(root, 0)[0];// root为头,高度0开始,[0]==root.val,[1]==height
	}

	private int[] f(TreeNode root, int h) {
		if (root.left == null && root.right == null) {// 只有头
			return new int[] { root.val, h + 1 };
		}
		int[] left = null;
		if (root.left != null) {// 左边的答案
			left = this.f(root.left, h + 1);
		}
		int[] right = null;
		if (root.right != null) {// 右边的答案
			right = this.f(root.right, h + 1);
		}
		// 只有一头就返回一头
		if (left == null) {
			return right;
		}
		if (right == null) {
			return left;
		}
		// 两头都有, 返回高的
		if (left[1] < right[1]) {
			return right;
		} else
			return left;// 左边大和相等高度也返回左边
	}

	@Override
	public void debug1() {
		String str = "[1,2,3,4,null,5,6,null,null,7]";
		int e = 7;
		int r = this.findBottomLeftValue(TreeArray.array2tree(HelpDebug.str2array4(str)));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution513 so = new Solution513();
		so.debug1();

	}

}
